package leetcode;
import java.util.*;
/**
 * 46.全排列
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案.
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 *
 * 输入：nums = [1]
 * 输出：[[1]]
 */
public class Num_46 {
    List<Integer> inner = new ArrayList<>();
    List<List<Integer>> outter = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    public List<List<Integer>> permute(int[] nums) {
        dfs(nums);
        return outter;
    }

    private void dfs(int[] nums) {
        //边界条件
        if(inner.size() == nums.length){
            outter.add(new ArrayList<>(inner));
            return;
        }

        //每层都是从0开始搜索,⽽不是startIndex
        //需要set记录inner⾥都放了哪些元素了
        for (int i = 0; i < nums.length; i++) {
            //将没有添加过的元素填进去，再进行下一层
            if(set.add(nums[i])){
                //添加元素
                inner.add(nums[i]);
                //递归分支
                dfs(nums);
                //回溯删除
                inner.remove(inner.size() - 1);
                //并且要把set中的也要删除
                set.remove(nums[i]);
            }
        }
    }
}
